/**
 *  @file ListT.h
 */
#ifndef _LISTT_H_
#define _LISTT_H_

#include "../common/BaseObject.h"
#include "../common/DLHook.h"
#include "../exceptions/OutOfBoundsException.h"
#include "ICollection.h"
#include "sort/SortAlgorithm.h"

namespace cppflib
{

namespace collections
{

/**
 *   General List template
 *
 *   @note TYPE cannot be a C++ class but only primitive types such as 'char', 'int', ...
 */
template <class TYPE>
class ListT : public BaseObject, public ICollection
{
private:
    
    typedef struct _listnode
    {
       cppflib::DLHook hook;
       TYPE data;
    } listnode_t;

    u32_t count;     ///< number of elements in the list
    cppflib::DLHook *pListHead;  ///< points to list head
    cppflib::DLHook *pListTail;  ///< points to list tail

    //! for faster access in 'Get'
    mutable struct _curPointer
    {
       int curPos;
       cppflib::DLHook *pHook;
    } curPointer;

    /**
     *  Get original node pointer
     */
    listnode_t * GetNodePtr(cppflib::DLHook *pHook) const
    {
       return GETORGPTR(listnode_t, hook, pHook);
    }

    /**
     *  @param [in] nIndex -- index of updated element
     */
    void InvalidateCurPointer(int nIndex)
    {
       if (nIndex <= this->curPointer.curPos) {
          this->curPointer.curPos = -1;
          this->curPointer.pHook = NULL;
       }
    }

    bool IsCurPointerValid() const
    {
       return (this->curPointer.pHook != NULL);
    }

    void UpdateCurPointer(int pos, cppflib::DLHook *pHook) const
    {
       this->curPointer.curPos = pos;
       this->curPointer.pHook = pHook;
    }

    cppflib::DLHook * GetHookByIndex(int nIndex) const
    {
       cppflib::DLHook *pTemp = NULL;

       if (nIndex == 0) {
          pTemp = pListHead;
       }
       else if (nIndex == static_cast<int>(count - 1)) {
          pTemp = pListTail;
       }
       else if (IsCurPointerValid()) {
          int diff = nIndex - this->curPointer.curPos;
          pTemp = this->curPointer.pHook;
          
          if (diff >= 0) { // loop forward
             for (int i = 0 ; i < diff; ++i)
                pTemp = pTemp->GetNextEntry();
          }
          else {
             diff = -diff; // loop backward
             for (int i = 0 ; i < diff; ++i)
                pTemp = pTemp->GetPrevEntry();
          }

       }
       else {
       
          // cur pointer not valid, loop from beginning
          pTemp = pListHead;
          for (int i = 0 ; i < nIndex; ++i)
             pTemp = pTemp->GetNextEntry();
       }

       // update
       UpdateCurPointer(nIndex, pTemp);

       return pTemp;
    }

protected:
    typedef enum
    {
       ADD2HEAD,
       ADD2TAIL,
       INSERT,
    } inserttype_t;

    /**
     *  @param [in] nIndex -- only valid when insertType is INSERT
     *
     *  @return pointer to the hook of the newly added node
     */
    cppflib::DLHook * AddToList(TYPE data, inserttype_t insertType, int nIndex)
    {
       // this won't call constructor of DLHook but it's okay
       listnode_t *pNode = static_cast<listnode_t*>(::MRP_Calloc(1, sizeof(listnode_t)));
       pNode->data = data;
       switch (insertType) {
          case ADD2TAIL:
             pNode->hook.AddEntryToTail(&pListHead, &pListTail);
             InvalidateCurPointer(count);
             break;
          case ADD2HEAD:
             pNode->hook.AddEntryToHead(&pListHead, &pListTail);
             InvalidateCurPointer(0);
             break;
          case INSERT:
             cppflib::DLHook *pTemp = GetHookByIndex(nIndex);
             pNode->hook.InsertEntry(pTemp->GetPrevEntry(), pTemp);
             InvalidateCurPointer(nIndex);
             break;
       }

       ++count;

       return &pNode->hook;
    }

public:
    typedef util::BaseFuncPtr2T<int, TYPE, TYPE> CmpFunc;  ///< for method declaration
    typedef util::FuncPtr2T<int, TYPE, TYPE> CmpFuncS;     ///< for actual variable declaration

    typedef util::BaseFuncPtr2T<bool, int, TYPE&> ForEachFunc;
    typedef util::FuncPtr2T<bool, int, TYPE&> ForEachFuncS;
    
private:
    /**
     *  This one is used internally -- casting data to original type before
     *  passing to user provided function for comparison. 
     */
    class PrivateSortCmpFunc : public sort::SortCmpFunc
    {
    private:
       const CmpFunc &orgCmpFunc;
    private: 
       PrivateSortCmpFunc() { } 
    public: 
       explicit PrivateSortCmpFunc(const CmpFunc &f) : orgCmpFunc(f) { } 
       virtual ~PrivateSortCmpFunc() { } 
       virtual int operator() (ptrany_t a1, ptrany_t a2) const 
       { 
          TYPE a = *reinterpret_cast<TYPE*>(a1);
          TYPE b = *reinterpret_cast<TYPE*>(a2);
          return orgCmpFunc(a, b); 
       } 
    };


public:
    ListT(void)
    {
       count = 0;
       pListHead = pListTail = NULL;
       UpdateCurPointer(-1, NULL);
    }

    virtual ~ListT(void)
    {
       Clear();
    }
    
    /**
     *  Add element to tail
     */
    void AddTail(TYPE data)
    {
       AddToList(data, ADD2TAIL, 0);
    }

    /**
     *  Add element to head
     */
    void AddHead(TYPE data)
    {
       AddToList(data, ADD2HEAD, 0);
    }

    /**
     *  Insert element at a particular position (zero based)
     */
    void Insert(int nIndex, TYPE data)
    {
       if (nIndex <= 0 || count == 0) {
          AddToList(data, ADD2HEAD, 0);
       }
       else if (nIndex >= static_cast<int>(count)) {
          AddToList(data, ADD2TAIL, 0);
       }
       else {
          AddToList(data, INSERT, nIndex);
       }
    }

    /**
     *  Remove an element
     *
     *  @return removed element
     */
    TYPE RemoveAt(int nIndex)
    {
       if (nIndex < 0 || nIndex >= static_cast<int>(count))
          throw exceptions::OutOfBoundsException(_S("Index out of bound"), -1);

       cppflib::DLHook *pTemp = GetHookByIndex(nIndex);

       pTemp->DeleteEntry(&pListHead, &pListTail);
       listnode_t *pNode = GetNodePtr(pTemp);
       TYPE ret = pNode->data;
       ::MRP_Release(pNode);
       InvalidateCurPointer(nIndex);
       --count;

       return ret;
    }

    /**
     *  Remove all elements
     */
    void Clear()
    {
       while (count > 0) {
          RemoveAt(0);
       }
    }

    /**
     *  Get value based on index (zero based)
     */
    TYPE Get(int nIndex) const
    {
       if (count == 0 || nIndex < 0 || nIndex >= static_cast<int>(count))
          throw exceptions::OutOfBoundsException(_S("Index out of bound"), -1);

       cppflib::DLHook *pTemp = GetHookByIndex(nIndex);
       return GetNodePtr(pTemp)->data;
    }

    /**
     *  Get element at list head
     */
    TYPE GetHead() const
    {
       return Get(0);
    }

    /**
     *  Get element at list tail
     */
    TYPE GetTail() const
    {
       return Get(count > 0 ? (count - 1) : 0);
    }

    /**
     *  Get number of element in the list
     */
    u32_t GetCount() const
    {
       return count;
    }

    /**
     *  Replace an existing value
     */
    TYPE Set(int nIndex, TYPE newVal)
    {
       if (count == 0 || nIndex < 0 || nIndex >= static_cast<int>(count))
          throw exceptions::OutOfBoundsException(_S("Index out of bound"), -1);

       cppflib::DLHook *pTemp = GetHookByIndex(nIndex);
       TYPE oldVal = GetNodePtr(pTemp)->data;
       GetNodePtr(pTemp)->data = newVal;
       return oldVal;   // return the old value
    }

    /**
     *  Make a copy of this list
     */
    ListT<TYPE> * Copy() const
    {
       ListT<TYPE> * pCopyList = new ListT<TYPE>();
       for (int i = 0; i < static_cast<int>(count); ++i) {
          pCopyList->AddTail(this->Get(i));
       }

       return pCopyList;
    }

    /**
     *  Swap element of 2 slots
     *  @implements ICollection::Swap
     */
    virtual void Swap(int i_1, int i_2)
    {
       if (count == 0 || i_1 < 0 || i_1 >= static_cast<int>(count) ||
                         i_2 < 0 || i_2 >= static_cast<int>(count))
          throw exceptions::OutOfBoundsException(_S("Index out of bound"), -1);

       cppflib::DLHook *pTemp1 = GetHookByIndex(i_1);
       cppflib::DLHook *pTemp2 = GetHookByIndex(i_2);

       // exchange value
       TYPE tempVal = GetNodePtr(pTemp1)->data;
       GetNodePtr(pTemp1)->data = GetNodePtr(pTemp2)->data;
       GetNodePtr(pTemp2)->data = tempVal;
    }
    /**
     *  Retrieve ith pointer to the element  
     *  @implements ICollection::Element
     */
    virtual ptrany_t Element(int i)
    {
       if (count == 0 || i < 0 || i >= static_cast<int>(count))
          throw exceptions::OutOfBoundsException(_S("Index out of bound"), -1);

       cppflib::DLHook *pTemp = GetHookByIndex(i);
       return reinterpret_cast<ptrany_t>(&(GetNodePtr(pTemp)->data));
    }

    /**
     *  Sort all list elements
     */
    void Sort(const CmpFunc &cmpFunc)
    {
       PrivateSortCmpFunc privateFunc(cmpFunc);
       sort::HeapSort(*this, 0, static_cast<int>(this->GetCount()), privateFunc);
    }

    /**
     *  Sort partial list elements
     */
    void Sort(int startIndex, int count, const CmpFunc &cmpFunc)
    {
       PrivateSortCmpFunc privateFunc(cmpFunc);
       sort::HeapSort(*this, startIndex, count, privateFunc);
    }

    /**
     *  Pass each item to a user provided function
     */
    void ForEach(const ForEachFunc &forEachFunc)
    {
       for (int i = 0; i < static_cast<int>(count); ++i) {
          cppflib::DLHook *pTemp = GetHookByIndex(i);
          if (! forEachFunc(i, GetNodePtr(pTemp)->data)) // break if return false
             break;
       }
    }
};

/**
 *  List of pointers to BaseObject derived classes
 */
template <class TYPE>
class ListCppObjT : public BaseObject, public ICollection
{

private:
    
    typedef struct _listnode
    {
       cppflib::DLHook hook;
       BaseObject *pData;
    } listnode_t;

    u32_t count;     ///< number of elements in the list
    cppflib::DLHook *pListHead;  ///< points to list head
    cppflib::DLHook *pListTail;  ///< points to list tail

    //! for faster access in 'Get'
    mutable struct _curPointer
    {
       int curPos;
       cppflib::DLHook *pHook;
    } curPointer;

    /**
     *  @param [in] nIndex -- index of updated element
     */
    void InvalidateCurPointer(int nIndex)
    {
       if (nIndex <= this->curPointer.curPos) {
          this->curPointer.curPos = -1;
          this->curPointer.pHook = NULL;
       }
    }


protected:
    typedef enum
    {
       ADD2HEAD,
       ADD2TAIL,
       INSERT,
    } inserttype_t;

    /**
     *  Get original node pointer
     */
    listnode_t * GetNodePtr(cppflib::DLHook *pHook) const
    {
       return GETORGPTR(listnode_t, hook, pHook);
    }

    /**
     *  @param [in] nIndex -- only valid when insertType is INSERT
     *
     *  @return pointer to the hook of the newly added node
     */
    cppflib::DLHook * AddToList(TYPE *pData, inserttype_t insertType, int nIndex)
    {
       cppmempool::Retain(pData);  // increase ref count

       // this won't call constructor of DLHook but it's okay
       listnode_t *pNode = static_cast<listnode_t*>(::MRP_Calloc(1, sizeof(listnode_t)));
       pNode->pData = pData;
       switch (insertType) {
          case ADD2TAIL:
             pNode->hook.AddEntryToTail(&pListHead, &pListTail);
             InvalidateCurPointer(count);
             break;
          case ADD2HEAD:
             pNode->hook.AddEntryToHead(&pListHead, &pListTail);
             InvalidateCurPointer(0);
             break;
          case INSERT:
             cppflib::DLHook *pTemp = GetHookByIndex(nIndex);
             pNode->hook.InsertEntry(pTemp->GetPrevEntry(), pTemp);
             InvalidateCurPointer(nIndex);
             break;
       }

       ++count;

       return &pNode->hook;
    }

    /**
     *  Remove from list
     */ 
    void RemoveFromList(cppflib::DLHook *pHook, int index)
    {
       pHook->DeleteEntry(&pListHead, &pListTail);
       listnode_t *pNode = GetNodePtr(pHook);
       cppmempool::Release(pNode->pData);     // decrease ref count
       ::MRP_Release(pNode);
       InvalidateCurPointer(index);
       --count;
    }

private: 
    
    void UpdateCurPointer(int pos, cppflib::DLHook *pHook) const
    {
       this->curPointer.curPos = pos;
       this->curPointer.pHook = pHook;
    }

    bool IsCurPointerValid() const
    {
       return (this->curPointer.pHook != NULL);
    }

    cppflib::DLHook * GetHookByIndex(int nIndex) const
    {
       cppflib::DLHook *pTemp = NULL;

       if (nIndex == 0) {
          pTemp = pListHead;
       }
       else if (nIndex == static_cast<int>(count - 1)) {
          pTemp = pListTail;
       }
       else if (IsCurPointerValid()) {
          int diff = nIndex - this->curPointer.curPos;
          pTemp = this->curPointer.pHook;
          
          if (diff >= 0) { // loop forward
             for (int i = 0 ; i < diff; ++i)
                pTemp = pTemp->GetNextEntry();
          }
          else {
             diff = -diff; // loop backward
             for (int i = 0 ; i < diff; ++i)
                pTemp = pTemp->GetPrevEntry();
          }

       }
       else {
       
          // cur pointer not valid, loop from beginning
          pTemp = pListHead;
          for (int i = 0 ; i < nIndex; ++i)
             pTemp = pTemp->GetNextEntry();
       }

       // update
       UpdateCurPointer(nIndex, pTemp);

       return pTemp;
    }

    cppflib::DLHook * GetHookByData(const TYPE &data)
    {
       cppflib::DLHook *pTemp = pListHead;

       while (pTemp) {
          listnode_t * pNode = GetNodePtr(pTemp);
          if (pNode->pData->Equals(data))
             break;

          pTemp = pTemp->GetNextEntry();
       }

       return pTemp;
    }

public:
    typedef util::BaseFuncPtr2T<int, TYPE*, TYPE*> CmpFunc;
    typedef util::FuncPtr2T<int, TYPE*, TYPE*> CmpFuncS;

    typedef util::BaseFuncPtr2T<bool, int, TYPE*&> ForEachFunc;
    typedef util::FuncPtr2T<bool, int, TYPE*&> ForEachFuncS;
    
private:
    /**
     *  This one is used internally -- casting data to original type before
     *  passing to user provided function for comparison. 
     */
    class PrivateSortCmpFunc : public sort::SortCmpFunc
    {
    private:
       const CmpFunc &orgCmpFunc;
    private: 
       PrivateSortCmpFunc() { } 
    public: 
       explicit PrivateSortCmpFunc(const CmpFunc &f) : orgCmpFunc(f) { } 
       virtual ~PrivateSortCmpFunc() { } 
       virtual int operator() (ptrany_t a1, ptrany_t a2) const 
       { 
          TYPE* a = reinterpret_cast<TYPE*>(a1);
          TYPE* b = reinterpret_cast<TYPE*>(a2);
          return orgCmpFunc(a, b); 
       } 
    };

public:
    ListCppObjT(void)
    {
       count = 0;
       pListHead = pListTail = NULL;
       UpdateCurPointer(-1, NULL);
    }
    
    virtual ~ListCppObjT(void)
    {
       Clear();
    }

    /**
     *  Add element to tail
     */
    void AddTail(TYPE *pData)
    {
       AddToList(pData, ADD2TAIL, 0);
    }

    /**
     *  Add element to head
     */
    void AddHead(TYPE *pData)
    {
       AddToList(pData, ADD2HEAD, 0);
    }

    /**
     *  Insert element at a particular position (zero based)
     */
    void Insert(int nIndex, TYPE *pData)
    {
       if (nIndex <= 0 || count == 0) {
          AddToList(pData, ADD2HEAD, 0);
       }
       else if (nIndex >= static_cast<int>(count)) {
          AddToList(pData, ADD2TAIL, 0);
       }
       else {
          AddToList(pData, INSERT, nIndex);
       }
    }

    /**
     *  Remove an element by index
     */
    void RemoveAt(int nIndex)
    {
       if (nIndex < 0 || nIndex >= static_cast<int>(count))
          throw exceptions::OutOfBoundsException(_S("Index out of bound"), -1);

       cppflib::DLHook *pTemp = GetHookByIndex(nIndex);
       RemoveFromList(pTemp, nIndex);
    }

    /**
     *  Remove an element
     */
    bool Remove(const TYPE &data)
    {
       cppflib::DLHook *pTemp = GetHookByData(data);
       if (!pTemp)
          return false;

       RemoveFromList(pTemp, 0);
       return true;
    }

    /**
     *  Remove all elements
     */
    void Clear()
    {
       while (count > 0) {
          RemoveAt(0);
       }
    }
    
    /**
     *  Get value based on index (zero based)
     */
    TYPE *Get(int nIndex) const
    {
       if (count == 0 || nIndex < 0 || nIndex >= static_cast<int>(count))
          throw exceptions::OutOfBoundsException(_S("Index out of bound"), -1);

       cppflib::DLHook *pTemp = GetHookByIndex(nIndex);
       return static_cast<TYPE*>(GetNodePtr(pTemp)->pData);
    }

    /**
     *  Get element at list head
     */
    TYPE *GetHead() const
    {
       return Get(0);
    }

    /**
     *  Get element at list tail
     */
    TYPE *GetTail() const
    {
       return Get(count > 0 ? (count - 1) : 0);
    }

    /**
     *  Get number of element in the list
     */
    u32_t GetCount() const
    {
       return count;
    }

    /**
     *  Replace an existing value
     */
    void Set(int nIndex, TYPE* newVal)
    {
       if (count == 0 || nIndex < 0 || nIndex >= static_cast<int>(count))
          throw exceptions::OutOfBoundsException(_S("Index out of bound"), -1);

       cppflib::DLHook *pTemp = GetHookByIndex(nIndex);
       cppmempool::Retain(newVal);
       cppmempool::Release(GetNodePtr(pTemp)->pData);
       
       GetNodePtr(pTemp)->pData = newVal;
    }

    /**
     *  Make a copy of this list -- elements are just shallow copy
     */
    ListCppObjT<TYPE> * Copy() const
    {
       ListCppObjT<TYPE> * pCopyList = new ListCppObjT<TYPE>();
       for (int i = 0; i < static_cast<int>(count); ++i) {
          pCopyList->AddTail(this->Get(i));
       }

       return pCopyList;
    }

    /**
     *  Swap element of 2 slots
     *  @implements ICollection::Swap
     */
    virtual void Swap(int i_1, int i_2)
    {
       if (count == 0 || i_1 < 0 || i_1 >= static_cast<int>(count) ||
                         i_2 < 0 || i_2 >= static_cast<int>(count))
          throw exceptions::OutOfBoundsException(_S("Index out of bound"), -1);

       cppflib::DLHook *pTemp1 = GetHookByIndex(i_1);
       cppflib::DLHook *pTemp2 = GetHookByIndex(i_2);

       // exchange value
       BaseObject *pTempVal = GetNodePtr(pTemp1)->pData;
       GetNodePtr(pTemp1)->pData = GetNodePtr(pTemp2)->pData;
       GetNodePtr(pTemp2)->pData = pTempVal;
    }
    /**
     *  Retrieve ith pointer to the element  
     *  @implements ICollection::Element
     */
    virtual ptrany_t Element(int i)
    {
       if (count == 0 || i < 0 || i >= static_cast<int>(count))
          throw exceptions::OutOfBoundsException(_S("Index out of bound"), -1);

       cppflib::DLHook *pTemp = GetHookByIndex(i);
       return reinterpret_cast<ptrany_t>(GetNodePtr(pTemp)->pData);
    }

    /**
     *  Sort all list elements
     */
    void Sort(const CmpFunc &cmpFunc)
    {
       PrivateSortCmpFunc privateFunc(cmpFunc);
       sort::HeapSort(*this, 0, static_cast<int>(this->GetCount()), privateFunc);
    }

    /**
     *  Sort partial list elements
     */
    void Sort(int startIndex, int count, const CmpFunc &cmpFunc)
    {
       PrivateSortCmpFunc privateFunc(cmpFunc);
       sort::HeapSort(*this, startIndex, count, privateFunc);
    }

    /**
     *  Pass each item to a user provided function
     */
    void ForEach(const ForEachFunc &forEachFunc)
    {
       for (int i = 0; i < static_cast<int>(count); ++i) {
          cppflib::DLHook *pTemp = GetHookByIndex(i);
          TYPE *p = static_cast<TYPE*>(GetNodePtr(pTemp)->pData);
          if (! forEachFunc(i, p)) // break if return false
             break;
       }
    }
};


/**
 *  Declare some list factory type
 */
typedef ListT<char> ListChar;
typedef ListT<u8_t> ListByte;
typedef ListT<wc_t> ListWChar;
typedef ListT<short> ListShort;
typedef ListT<u16_t> ListUShort;
typedef ListT<int> ListInt;
typedef ListT<u32_t> ListUInt;
typedef ListT<long> ListLong;
typedef ListT<unsigned long> ListULong;
typedef ListT<i64_t> ListInt64;
typedef ListT<u64_t> ListUInt64;
typedef ListT<bool> ListBool;
typedef ListT<float> ListFloat;
typedef ListT<double> ListDouble;
typedef ListT<ptr_t> ListPtr;




} // end of namespace collections


} // end of namespace cppflib


#endif
